package main.leetcode.primary.from001to100;

/**
 * 14.最长公共前缀
 *
 * <p>编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
 *
 * <p>示例 1: 输入: ["flower","flow","flight"] 输出: "fl"
 *
 * <p>示例 2: 输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。
 *
 * <p>说明: 所有输入只包含小写字母 a-z 。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-common-prefix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex14 {
    public static void main(String[] args) {
        String[] strings = {"flower", "flow", "flight"};
        System.out.println(longestCommonPrefix3(strings));
    }

    public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        int minIndex = 0, i, j;
        for (i = 0; i < strs.length; i++)
            if (strs[i].length() < strs[minIndex].length()) minIndex = i;
        for (i = 0; i < strs[minIndex].length(); i++)
            for (j = 1; j < strs.length; j++)
                if (strs[j].charAt(i) != strs[0].charAt(i)) return strs[0].substring(0, i);
        return strs[minIndex];
    }

    // 水平扫描法
    public static String longestCommonPrefix1(String[] strs) {
        if (strs.length == 0) return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++)
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.length() == 0) return "";
            }
        return prefix;
    }

    public static String longestCommonPrefix3(String[] strs) {
        if (strs.length == 0) return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            prefix = getCommonPrefix(strs[i], prefix);
            if ("".equals(prefix)) return prefix;
        }
        return prefix;
    }

    private static String getCommonPrefix(String str, String prefix) {
        StringBuilder newPrefix = new StringBuilder();
        for (int i = 0; i < Math.min(str.length(), prefix.length()); i++) {
            if (str.charAt(i) != prefix.charAt(i)) return prefix.substring(0, i);
            newPrefix.append(prefix.charAt(i));
        }
        return newPrefix.toString();
    }
}
